'''dijkstra算法，适用于正向边，对处理过的边不能再找到其最短带权（cost最小）的路径
'''

'''构建三个表，graph，cost，present表，分别记录图路径，权重，存放父节点的表'''
graph={}
graph["start"]={}
graph["start"]["a"]=6
graph["start"]["b"]=2
graph["a"]={}
graph["a"]["end"]=1
graph["b"]={}
graph["b"]["a"]=3
graph["b"]["end"]=5
graph["end"]={}

costs={}
infinity=float("inf")
costs["a"]=6
costs["b"]=2
costs["end"]=infinity

parents={}
parents["a"]="start"
parents["b"]="start"
parents['end']=None

processed=[]  #存放已经处过的节点

def find_lowed_node(costs):
    '寻找cost最低的节点'
    lowest_cost=float("inf")
    lowest_cost_node=None
    for node in costs:
        cost=costs[node]
        if cost<lowest_cost and node not in processed:  #小于当前最低cost并且没有被处理过
            lowest_cost=cost
            lowest_cost_node=node
    return lowest_cost_node

def dijkstra():
    node=find_lowed_node(costs)
    while node is not None :  #结束条件：所有节点均被处理过
        cost=costs[node]
        neighbors=graph[node]
        for neighbor in neighbors.keys() :
            new_cost=cost+costs[neighbor]
            if costs[neighbor]>new_cost:
                costs[neighbor]=new_cost
                parents[neighbor]=node
        processed.append(node)
        node=find_lowed_node(costs)
    print("到终点的路径",processed)

dijkstra()